#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <limits.h>

#define ROWS 10
#define COLS 10
#define WALL '#'
#define PATH ' '
#define START 'S'
#define END 'E'
#define EMPTY '.'
#define VISITED 'V'
#define QUEUE_SIZE 100

typedef struct {
    int x, y;
} Point;

typedef struct {
    Point points[QUEUE_SIZE];
    int front, rear;
} Queue;

void initializeQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

bool isEmpty(Queue* q) {
    return q->front == -1;
}

bool isFull(Queue* q) {
    return q->rear == QUEUE_SIZE - 1;
}

void enqueue(Queue* q, Point p) {
    if (!isFull(q)) {
        q->rear++;
        q->points[q->rear] = p;
    }
    else {
        printf("Queue is full!\n");
    }
}

Point dequeue(Queue* q) {
    if (!isEmpty(q)) {
        Point p = q->points[q->front];
        q->front++;
        return p;
    }
    else {
        Point empty = { -1, -1 };
        return empty;
    }
}

int isValid(char maze[ROWS][COLS], int x, int y) {
    return (x >= 0 && x < ROWS && y >= 0 && y < COLS && maze[x][y] != WALL && maze[x][y] != VISITED);
}

void generateRandomMaze(char maze[ROWS][COLS]) {
    srand(time(NULL));
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            maze[i][j] = (rand() % 2 == 0) ? WALL : PATH;
        }
    }
    maze[0][0] = START;
    maze[ROWS - 1][COLS - 1] = END;
}

bool solveMaze(char maze[ROWS][COLS]) {
    Queue q;
    initializeQueue(&q);

    Point start = { 0, 0 };
    Point direction[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
    Point p;

    maze[start.x][start.y] = VISITED;
    enqueue(&q, start);

    while (!isEmpty(&q)) {
        p = dequeue(&q);

        if (maze[p.x][p.y] == END) {
            return true;
        }

        for (int i = 0; i < 4; i++) {
            int newX = p.x + direction[i].x;
            int newY = p.y + direction[i].y;

            if (isValid(maze, newX, newY)) {
                maze[newX][newY] = VISITED;
                enqueue(&q, (Point) { newX, newY });
            }
        }
    }

    return false;
}

void printMaze(char maze[ROWS][COLS]) {
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%c ", maze[i][j]);
        }
        printf("\n");
    }
}

int main() {
    char maze[ROWS][COLS];
    generateRandomMaze(maze);
    printf("Generated Maze:\n");
    printMaze(maze);

    if (solveMaze(maze)) {
        printf("\nSolution found:\n");
    }
    else {
        printf("\nNo solution found.\n");
    }

    printMaze(maze);
    return 0;
}